function quickSort(arr, startIndex, endIndex) {
    //递归结束条件：startIndex大于或等于endIndex
    if (startIndex >= endIndex) {
      return;
    }
    //得到基准元素位置
    let pivotIndex = partition(arr, startIndex, endIndex);
    //根据基准元素，分成两部分进行递归排序
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, endIndex);
  }
  /**
   * 分治(双边循环法)
   * @param {*} arr 
   * @param {*} startIndex 
   * @param {*} endIndex 
   * @returns 
   */
  function partition(arr, startIndex, endIndex) {
    //取第1个位置的元素作为基准元素
    let pivot = arr[startIndex];
    let left = startIndex;
    let right = endIndex;
    while(left !=right){
      //控制right指针向左移动
      while(left < right && arr[right] >= pivot){
        right--;
      }
      //控制left指针向右移动
      while(left < right && arr[left] <= pivot){
        left++;
      }
      //交换left和right指针所指向的元素
      if(left < right){
        [arr[left], arr[right]] = [arr[right], arr[left]];
      }
    }
    //pivot 和 指针重合点所指向的元素交换
    [arr[startIndex], arr[left]] = [arr[left], arr[startIndex]];
    return left;
  }
  let arr = [4, 4, 6, 5, 3, 2, 8, 1];
  quickSort(arr, 0, arr.length - 1);
  console.log(arr);